﻿using System;
using System.Collections.Generic;
using System.Threading;
using System.Collections;
using System.Text;
using OliveChess;

using Bitboard = System.UInt64;

namespace OliveChess
{
    using System.Runtime.InteropServices;
    using System.Diagnostics;

    class Engine
    {
        const int WHITE = 0;
        const int BLACK = 1;

        const int VALUE_INFINITE = 99999; // in order to distinguish INFINITE and MATE usage
        const int VALUE_MATE = 30000;
        const int VALUE_DRAW = 0;
        const int HASH_MIN_DEPTH = 2;

        const int QUIESCE_DEPTH = 2;

        // aspiration window minimal depth
        const int ASPWINDOW_MIN_DEPTH = 5;

        private readonly Thread mainThread;
        private readonly Thread clockThread;
        private bool debugMode;

        public bool debugNegmax;
        public bool debugIterativeAB;
        public bool debugQuiesce;
        public bool debugNegascout;
        
        // transposition table
        //public bool useTT;
        //public TranspositionTable TT;

        private Position currentPosition;
        private int currentTurn;
        Stopwatch watch;

        private long nodeMaxNumber;
        private long nbProcessedNodes;
        private int selectiveDepth;

        private BrainMode brainMode;
        private BrainStatus brainStatus;
        private int depthLevel;
        private long thinkDelay;

        private TimeSpan wtime; //total time left for white in millisec
        private TimeSpan btime; //total time left for black in millisec
        private TimeSpan winc;
        private TimeSpan binc;

        private bool isVerbose;

        private bool isSmartTiming;
        private bool isSearchMove;

        // New Alpha-beta implementation
        List<Move> moves = new List<Move>();
        List<Tuple<Move, int, Stack<Move>>> scores = new List<Tuple<Move, int, Stack<Move>>>();

        /*
        // Coefficient of each piece in centipawn -- OLD IMPLEMENTATION
        // {WP,WN,WB,WR,WQ,WK,BP,BN,BB,BR,BQ,BK,None}
        private static int[] coeff = { 85, 325, 325, 500, 975, 10000000, -85, -325, -325, -500, -975, -10000000 };
        private static int[] W_coeff = { 85, 325, 325, 500, 975, 10000000, -85, -325, -325, -500, -975, -10000000 };
        private static int[] B_coeff = { -85, -325, -325, -500, -975, -10000000, 85, 325, 325, 500, 975, 10000000 };
        */

        // new bitboard related coeffs
        // {W_all,B_all, WP,BP,WN,BN,WB,BB,WR,BR,WQ,BQ,WK,BK,None}
        private static int[] coeff      = { 0, 0, 85, -85, 325, -325, 325, -325, 500, -500, 975, -975, 10000000, -10000000 };
        private static int[] W_coeff    = { 0, 0, 85, -85, 325, -325, 325, -325, 500, -500, 975, -975, 10000000, -10000000 };
        private static int[] B_coeff    = { 0, 0, -85, 85, -325, 325, -325, 325, -500, 500, -975, 975, -10000000, 10000000 };
        
        private Move? bestMove;
        private int bestScore;
        //private int maxTTsize;

        public Engine()
        {
            /*
            // Transposition table
            TT = new TranspositionTable();
            useTT = true;
            */

            // new alphabeta implementation
            moves = new List<Move>();
            scores = new List<Tuple<Move, int, Stack<Move>>>();

            // Stopwatch (timer)
            watch = new Stopwatch();
            isSearchMove = false;

            // Smart timing (default = true)
            isSmartTiming = false;

            this.brainStatus = BrainStatus.PAUSED;
            this.currentPosition = new Position();

            // TOD0 debug init = Blitz 2'+6"/ply - to be removed
            this.SetWtime(120000);
            this.SetWinc(6000);
            this.SetBtime(120000);
            this.SetBinc(6000);
            SetStartPosition();

            mainThread = new Thread(new ThreadStart(this.BrainMainThreadLoop));
            clockThread = new Thread(new ThreadStart(this.ClockThreadLoop));

            // Launching threads
            mainThread.Start();
            clockThread.Start();
        }

        public void Quit()
        {
            mainThread.Abort();
            clockThread.Abort();
        }

        // This thread function manage the change of status of the brain
        // When searching we only need to check the brainStatus
        // (time elapsed is available via the watch variable)
        private void ClockThreadLoop()
        {
            while (true)
            {
                while (brainStatus != BrainStatus.THINKING)
                {
                    Thread.Sleep(100);
                }

                if(brainMode == BrainMode.MOVETIME_MODE
                    || brainMode == BrainMode.ADJUSTTIME_MODE)
                {
                    // the search can be manually stopped via the command line
                    // so a Sleep(thinkDelay) is not accurate enough
                    // we need to check regularly if the brain was not stop by another way
                    while (watch.ElapsedMilliseconds < thinkDelay
                        && brainStatus != BrainStatus.PAUSED)
                    {
                        Thread.Sleep(100);
                    } 
                    brainStatus = BrainStatus.PAUSED;
                }
            }
        }

        // Main thread - feeding nodes
        private void BrainMainThreadLoop()
        {
            // This threads will always run
            while (true)
            {
                // wait loop
                while (brainStatus != BrainStatus.THINKING)
                {
                    Thread.Sleep(100);
                }


                // Thread main task

                // global value
                bestMove = null;
                bestScore = 0;
                int depth;
                switch (brainMode)
                {
                    case BrainMode.ADJUSTTIME_MODE:
                    case BrainMode.MOVETIME_MODE:
                        
                        depth = 1;
                        ReturnCode searchResult = ReturnCode.OK;
                        while (searchResult == ReturnCode.OK
                            && brainStatus == BrainStatus.THINKING)
                        {
                            searchResult = Search(ref currentPosition, depth);
                            depth++;
                        }

                        break;
                    case BrainMode.MATE_MODE:
                    case BrainMode.DEPTH_MODE:
                        //depth = 1;
                        depth = 3; // fro debug ONLY
                        while (brainStatus == BrainStatus.THINKING && depth <= depthLevel)
                        {
                            Search(ref currentPosition, depth);
                            depth++;
                        }
                        break;
                    case BrainMode.NODES_MODE:
                        depth = 1;
                        while (brainStatus == BrainStatus.THINKING && nbProcessedNodes < nodeMaxNumber)
                        {
                            Search(ref currentPosition, depth);
                            depth++;
                        }
                        break;
                    case BrainMode.INFINITE_MODE:
                        depth = 1;
                        while (brainStatus == BrainStatus.THINKING)
                        {
                            Search(ref currentPosition, depth);
                            depth++;
                        }
                        break;
                    default:
                        brainStatus = BrainStatus.PAUSED;
                        break;
                }
                this.Stop();

                if (bestMove != null)
                {
                    // Display best move
                    Console.WriteLine("bestmove " + bestMove.ToString());
                }
                else
                {
                    // Display no move
                    Console.WriteLine("bestmove -");
                }

            }
        }


        private ReturnCode Search(ref Position position, int depth)
        {
            // TODO : global variables should be declared as local for multithreading
            selectiveDepth = 0;
            Position pos = new Position(ref position);
            ReturnCode returnCode = ReturnCode.KO;

            int alpha = -VALUE_INFINITE;
            int beta = VALUE_INFINITE;

            scores.Clear();
            // search for each move
            currentTurn = pos.GetTurn();
            nbProcessedNodes = moves.Count;
            foreach (Move currmove in moves)
            {
                pos.Play(currmove);
                // Next ply is for the opponent
                int score = 0;
                Stack<Move> pv = new Stack<Move>();
                pv.Push(currmove);
                // TODO remove iterative statement FOR DEBUG ONLY ******************
                if (debugNegmax)
                {
                    // WORKING
                    returnCode = AlphaBetaNegmaxMin(ref score, ref pos, ref pv, alpha, beta, 1, depth);

                }
                else if (debugIterativeAB)
                    returnCode = AlphaBetaIterative(ref score, ref pos, ref pv, alpha, beta, 1, depth);
                else if (debugNegascout)
                {
                    returnCode = NegaScout(ref score, ref pos, ref pv, alpha, beta, 1, depth);
                    if (((currentTurn + depth) % 2) == 0)
                        score *= -1;
                }
                else
                    returnCode = AlphaBetaMin(ref score, ref pos, ref pv, alpha, beta, 1, depth);
                    //returnCode = AlphaBetaMinMax(ref score, ref pos, ref pv, alpha, beta, 1, depth, false);
                

                // TODO: inclue directly this code in alphabeta method
                /*
                    if (depth < ASPWINDOW_MIN_DEPTH)
                    {
                        // ASPIRATION WINDOW METHOD
                        // TO BE TESTED
                        // A guess window based on the previous searches is used for the alpha/beta search


                        // 100 should be replaced by PAWN_VALUE
                        //float depthFactor = 2*depth;
                        int deltaMin = 100 * (1 / 2);
                        int deltaMax = 100 * (1 / 2);
                        int lowerBound;
                        int upperBound;
                        do
                        {
                            lowerBound = bestScore - deltaMin;
                            upperBound = bestScore + deltaMax;
                            returnCode = AlphaBetaMin(ref score, ref pos, ref pv, lowerBound, upperBound, 1, depth);
                            if (score < lowerBound)
                                deltaMin *= 2;
                            if (score > lowerBound)
                                deltaMax *= 2;
                        } while ((score > lowerBound) || (score < upperBound));

                    }

                 * */

                pos.Unplay(currmove);
                if (returnCode != ReturnCode.OK)
                    break;
                Tuple<Move, int, Stack<Move>> movescore = new Tuple<Move, int, Stack<Move>>(currmove, score, pv);
                scores.Add(movescore);
            }

            // sort move by score
            if (returnCode == ReturnCode.OK)
            {
                // Update only if search was fully performed
                Sort(scores);
                bestMove = scores[0].Item1;
                bestScore = scores[0].Item2;
                DisplayBestPv(scores[0], depth, selectiveDepth);
                if(debugMode)
                    DisplayScores(scores, depth);
            }
            return returnCode;
        }

        private ReturnCode AlphaBetaMinMax(ref int score, ref Position pos, ref Stack<Move> pv, int alpha, int beta, int depth, int maxDepth, bool maxPlayer)
        {
            if (brainStatus != BrainStatus.THINKING)
                return ReturnCode.STOPTHINKING; // quick exit
            String pfen = pos.GetPseudoFEN();
            if (depth == maxDepth)
            {
                score = EvaluateRelative(pos, currentTurn);
                return ReturnCode.OK;
            }
            List<Move> moves = new List<Move>();
            GetLegalMoves(ref pos, ref moves);


            if(maxPlayer){
                if (moves.Count == 0)
                    if (IsCheck(ref pos))
                    {
                        score = -VALUE_MATE + depth;
                        return ReturnCode.OK;
                    }
                    else
                    {
                        score = VALUE_DRAW;
                        return ReturnCode.OK;
                    }
                nbProcessedNodes += moves.Count;
                foreach (Move m in moves)
                {
                    pos.Play(m);
                    ReturnCode returnCode = AlphaBetaMinMax(ref score, ref pos, ref pv, alpha, beta, depth + 1, maxDepth,!maxPlayer);
                    pos.Unplay(m);
                    if (returnCode != ReturnCode.OK)
                        return returnCode;
                    if (score >= beta)
                    {
                        score = beta;   // fail hard beta-cutoff
                        return ReturnCode.OK;
                    }
                    if (score > alpha)
                    {
                        alpha = score; // alpha acts like max in MiniMax
                    }
                }
                score = alpha;
                return ReturnCode.OK;
            }
            else
            {
                if (moves.Count == 0)
                    if (IsCheck(ref pos))
                    {
                        score = VALUE_MATE - depth;
                        return ReturnCode.OK;
                    }
                    else
                    {
                        score = VALUE_DRAW;
                        return ReturnCode.OK;
                    }
                nbProcessedNodes += moves.Count;
                //TranspTableEntry tte = new TranspTableEntry();
                foreach (Move m in moves)
                {
                    pos.Play(m);
                    ReturnCode returnCode = AlphaBetaMinMax(ref score, ref pos, ref pv, alpha, beta, depth + 1, maxDepth,!maxPlayer);
                    pos.Unplay(m);
                    if (returnCode != ReturnCode.OK)
                        return returnCode;
                    if (score <= alpha)
                    {
                        /*// TT part
                        if (useTT)
                        {
                            tte.nodeType = NodeType.ALL_NODE; //alpha-cutoff
                            tte.score = alpha;
                            tte.bestMove = m;
                            TT.Add(pos.GetPseudoFEN(), tte);
                        }*/
                        score = alpha; // fail hard alpha-cutoff
                        return ReturnCode.OK;
                    }
                    if (score < beta)
                    {
                        /*if (useTT)
                        {
                            tte.score = beta;
                            tte.bestMove = m;
                        }*/
                        beta = score; // beta acts like min in MiniMax
                    }
                }
                /*if (useTT)
                {
                    tte.nodeType = NodeType.PV_NODE; //in bounds score
                    //tte.score = beta; //already stored
                    //tte.bestMove = m;
                    TT.Add(pos.GetPseudoFEN(), tte);
                }*/
                score = beta;
                return ReturnCode.OK;
            }

        }




        // Display pv line
        private void DisplayBestPv(Tuple<Move, int, Stack<Move>> scoreMoves, int depth, int seldepth)
        {
            StringBuilder info = new StringBuilder("info");
            
            // time
            long time = watch.ElapsedMilliseconds;
            info.Append(" time ");
            info.Append(time);

            // depth
            info.Append(" depth ");
            info.Append(depth);
            
            // selectdepth
            if (selectiveDepth > depth)
            {
                info.Append(" seldepth ");
                info.Append(seldepth);
            }

            // nodes
            info.Append(" nodes ");
            info.Append(nbProcessedNodes);

            // nps
            long nps = (time==0)?0:(nbProcessedNodes * 1000) / time;
            info.Append(" nps ");
            info.Append(nps);

            // score
            info.Append(" score ");
            info.Append(ScoreToString(scoreMoves.Item2));
            // TODO: manage mate display (no cp)

            // pv (move list)
            info.Append(" pv ");
            foreach (Move m in scoreMoves.Item3)
            {
                info.Append(m.ToString());
                info.Append(" ");
            }

            Console.WriteLine(info.ToString());
        }

        private void DisplayScores(List<Tuple<Move, int, Stack<Move>>> scores, int depth)
        {
            int MOVES_PER_LINE = 5;
            Console.WriteLine("NEW MOVES EVALUATION -------------------- depth " + depth);
            int mvCount = 0;
            foreach (Tuple<Move, int, Stack<Move>> mscore in scores)
            {
                Console.Write(mscore.Item1.ToString() + "=" + ScoreToString(mscore.Item2) + " ");
                if ((mvCount + 1) % MOVES_PER_LINE == 0) Console.WriteLine();
                mvCount++;
            }
            Console.WriteLine();
            Console.WriteLine("-------------------------------------------------");
        }

        // Custom sort method
        // Bubble sort - can be improved
        // TODO: improve the sort method
        private void Sort(List<Tuple<Move, int, Stack<Move>>> scores)
        {
            int i;
            int j;
            Tuple<Move, int, Stack<Move>> temp;
            int x = scores.Count;

            for (i = (x - 1); i >= 0; i--)
            {
                for (j = 1; j <= i; j++)
                {
                    if (scores[j - 1].Item2 < scores[j].Item2)
                    {
                        temp = scores[j - 1];
                        scores[j - 1] = scores[j];
                        scores[j] = temp;
                    }
                }
            }
        }

        // AlphaBetaMax with error/break code
        /*
         * int alphaBeta( int alpha, int beta, int depthleft ) {
               if( depthleft == 0 ) return quiesce( alpha, beta );
               for ( all moves)  {
                  score = -alphaBeta( -beta, -alpha, depthleft - 1 );
                  if( score >= beta )
                     return beta;   //  fail hard beta-cutoff
                  if( score > alpha )
                     alpha = score; // alpha acts like max in MiniMax
               }
               return alpha;
            }*/

        /*
        // Self-called
        // must be used at root depth ???
        private ReturnCode AlphaBetaNegmaxMax(ref int score, ref Position pos, ref Stack<Move> pv, int alpha, int beta, int depth, int maxDepth)
        {
            if (brainStatus != BrainStatus.THINKING)
                return ReturnCode.STOPTHINKING; // quick exit
            String pfen = pos.GetPseudoFEN();
            if (depth == maxDepth)
            {
                score = EvaluateAbsolute(pos);
                return ReturnCode.OK;
            }
            List<Move> moves = new List<Move>();
            GetLegalMoves(ref pos, ref moves);
            if (moves.Count == 0)
                if (IsCheck(ref pos))
                {
                    score = ((currentTurn+maxDepth)%2 == 0 ? -1 : 1) * (VALUE_MATE - depth);
                    return ReturnCode.OK;
                }
                else
                {
                    score = VALUE_DRAW;
                    return ReturnCode.OK;
                }
            nbProcessedNodes += moves.Count;
            foreach (Move m in moves)
            {
                pos.Play(m);
                ReturnCode returnCode = AlphaBetaNegmaxMax(ref score, ref pos, ref pv, -beta, -alpha, depth + 1, maxDepth);
                score *= -1;
                pos.Unplay(m);
                if (returnCode != ReturnCode.OK)
                    return returnCode;
                if (score >= beta)
                {
                    score = beta;   // fail hard beta-cutoff
                    return ReturnCode.OK;
                }
                if (score > alpha)
                {
                    alpha = score; // alpha acts like max in MiniMax
                }
            }
            score = alpha;
            return ReturnCode.OK;
        }
        */

        // Self-called
        // TODO: problems for odd depth
        private ReturnCode AlphaBetaNegmaxMin(ref int score, ref Position pos, ref Stack<Move> pv, int alpha, int beta, int depth, int maxDepth)
        {
            if (brainStatus != BrainStatus.THINKING)
                return ReturnCode.STOPTHINKING; // quick exit
            String pfen = pos.GetPseudoFEN();
            if (depth == maxDepth)
            {
                //score = EvaluateAbsolute(pos);
                //score = EvaluateRelative(pos,(currentTurn +depth + 1)%2); //almost ok
                score = EvaluateRelative(pos, (currentTurn + depth + 1) % 2);
                return ReturnCode.OK;
            }
            List<Move> moves = new List<Move>();
            GetLegalMoves(ref pos, ref moves);
            if (moves.Count == 0)
                if (IsCheck(ref pos))
                {
                    score = (pos.GetTurn() == currentTurn) ? (depth - VALUE_MATE) : (VALUE_MATE - depth);
                    return ReturnCode.OK;
                }
                else
                {
                    score = VALUE_DRAW;
                    return ReturnCode.OK;
                }
            nbProcessedNodes += moves.Count;
            foreach (Move m in moves)
            {
                pos.Play(m);
                ReturnCode returnCode = AlphaBetaNegmaxMin(ref score, ref pos, ref pv, -beta, -alpha, depth + 1, maxDepth);
                score *= -1;
                pos.Unplay(m);
                if (returnCode != ReturnCode.OK)
                    return returnCode;
                if (score <= alpha)
                {
                    score = alpha;   // fail hard alpha-cutoff
                    return ReturnCode.OK;
                }
                if (score < beta)
                {
                    beta = score; // beta acts like max in MiniMax
                }
            }
            score = beta;
            return ReturnCode.OK;
        }

        // AlphaBetaMax with error/break code
        private ReturnCode AlphaBetaMax(ref int score, ref Position pos, ref Stack<Move> pv, int alpha, int beta, int depth, int maxDepth)
        {
            if (brainStatus != BrainStatus.THINKING) 
                return ReturnCode.STOPTHINKING; // quick exit
            String pfen = pos.GetPseudoFEN();
            if (depth == maxDepth)
            {
                //if (debugQuiesce)
                //    return QuiesceMin(ref score, ref pos, alpha, beta, depth + 1, maxDepth + 1 + QUIESCE_DEPTH);
                //else
                
                score = EvaluateRelative(pos, currentTurn);
                return ReturnCode.OK;
            }
            List<Move> moves = new List<Move>();
            GetLegalMoves(ref pos, ref moves);
            if (moves.Count == 0)
                if (IsCheck(ref pos))
                {
                    score = -VALUE_MATE +depth;
                    return ReturnCode.OK;
                }
                else
                {
                    score = VALUE_DRAW;
                    return ReturnCode.OK;
                }
            nbProcessedNodes += moves.Count;
            foreach (Move m in moves)
            {
                pos.Play(m);
                ReturnCode returnCode = AlphaBetaMin(ref score, ref pos, ref pv, alpha, beta, depth + 1, maxDepth);
                pos.Unplay(m);
                if (returnCode != ReturnCode.OK)
                    return returnCode;
                if (score >= beta)
                {
                    score = beta;   // fail hard beta-cutoff
                    return ReturnCode.OK;
                }
                if (score > alpha)
                {
                    alpha = score; // alpha acts like max in MiniMax
                }
            }
            score = alpha;
            return ReturnCode.OK;
        }

        // AlphaBetaMin with error/break code
        private ReturnCode AlphaBetaMin(ref int score, ref Position pos, ref Stack<Move> pv, int alpha, int beta, int depth, int maxDepth)
        {
            if (brainStatus != BrainStatus.THINKING)
                return ReturnCode.STOPTHINKING; // quick exit
            String pfen = pos.GetPseudoFEN();
            if (depth == maxDepth)
            {
                //if (debugQuiesce)
                //    return QuiesceMax(ref score, ref pos, alpha, beta, depth + 1, maxDepth+1+QUIESCE_DEPTH);
                //else
                score = EvaluateRelative(pos, currentTurn);
                return ReturnCode.OK;
            }
            List<Move> moves = new List<Move>();
            GetLegalMoves(ref pos, ref moves);
            if (moves.Count == 0)
                if (IsCheck(ref pos))
                {
                    score = VALUE_MATE - depth;
                    return ReturnCode.OK;
                }
                else
                {
                    score = VALUE_DRAW;
                    return ReturnCode.OK;
                }
            nbProcessedNodes += moves.Count;
            foreach (Move m in moves)
            {
                pos.Play(m);
                ReturnCode returnCode = AlphaBetaMax(ref score, ref pos, ref pv, alpha, beta, depth + 1, maxDepth);
                pos.Unplay(m);
                if (returnCode != ReturnCode.OK)
                    return returnCode;
                if (score <= alpha)
                {
                    score = alpha; // fail hard alpha-cutoff
                    return ReturnCode.OK;
                }
                if (score < beta)
                {
                    beta = score; // beta acts like min in MiniMax
                }
            }
            score = beta;
            return ReturnCode.OK;
        }
        

        /*
        private ReturnCode QuiesceMax(ref int score, ref Position pos, int alpha, int beta, int depth, int maxDepth)
        {
            if (depth > selectiveDepth)
                selectiveDepth = depth;

            int stand_pat = EvaluateRelative(pos, currentTurn);

            if (depth >= maxDepth)
            {
                score = stand_pat;
                return ReturnCode.OK;
            }


            if (stand_pat >= beta)
            {
                score = beta;
                return ReturnCode.OK;
            }
            if (alpha < stand_pat)
                alpha = stand_pat;

            List<Move> captures = new List<Move>();
            GetLegalMoves(ref pos, ref captures);

            foreach (Move m in captures)
            {

                pos.Play(m);
                //score = -Quiesce( -beta, -alpha );
                QuiesceMax(ref score, ref pos, -beta, -alpha, depth+1, maxDepth);
                pos.Unplay(m);

                if (score >= beta)
                {
                    score = beta;
                    return ReturnCode.OK;
                }
                if (score > alpha)
                    alpha = score;
            }
            score = alpha;
            return ReturnCode.OK;
        }


        private ReturnCode QuiesceMin(ref int score, ref Position pos, int alpha, int beta, int depth, int maxDepth)
        {
            if (depth > selectiveDepth)
                selectiveDepth = depth;

            int stand_pat = EvaluateRelative(pos, currentTurn);

            if (depth >= maxDepth)
            {
                score = stand_pat;
                return ReturnCode.OK;
            }

            if (stand_pat <= alpha)
            {
                score = alpha;
                return ReturnCode.OK;
            }
            if (beta > stand_pat)
                beta = stand_pat;

            List<Move> captures = new List<Move>();
            GetLegalMoves(ref pos, ref captures);

            foreach (Move m in captures)
            {
                // captures comes first in move list
                // when the first quiet move comes there is no more capture after that
                if (!m.IsCapture())
                    break;

                pos.Play(m);
                //score = -Quiesce( -beta, -alpha );
                QuiesceMax(ref score, ref pos, -beta, -alpha, depth+1, maxDepth);
                pos.Unplay(m);

                if (score <= alpha)
                {
                    score = alpha;
                    return ReturnCode.OK;
                }
                if (score < beta)
                    beta = score;
            }
            score = beta;
            return ReturnCode.OK;
        }
         * */

        /*function negascout(node, depth, α, β)
            if node is a terminal node or depth = 0
                return the heuristic value of node
            b := β                                             (* initial window is (-β, -α) *)
            foreach child of node
                score := -negascout (child, depth - 1, -b, -α)
                if α < score < β and child is not first child      (* check if null-window failed high *)
                    score := -negascout(child, depth - 1, -β, -α)  (* full re-search *)
                α := max(α, score)
                if α ≥ β
                    return α                                   (* Beta cut-off *)
                b := α + 1                                     (* set new null window *)
            return α*/
        private ReturnCode NegaScout(ref int score, ref Position pos, ref Stack<Move> pv, int alpha, int beta, int depth, int maxDepth)
        {
            if (brainStatus != BrainStatus.THINKING)
                return ReturnCode.STOPTHINKING; // quick exit
            String pfen = pos.GetPseudoFEN();
            if (depth == maxDepth)
            {
                score = EvaluateAbsolute(pos);
                return ReturnCode.OK;
            }
            int b = beta;
            List<Move> moves = new List<Move>();
            nbProcessedNodes += GetLegalMoves(ref pos, ref moves);
            
            bool isFirstMove = true;
            foreach (Move m in moves)
            {
                pos.Play(m);
                ReturnCode returnCode = NegaScout(ref score, ref pos, ref pv, -b , -alpha, depth + 1, maxDepth);
                pos.Unplay(m);
                if (returnCode != ReturnCode.OK)
                    return returnCode;

                if ((alpha < score) && (score < beta) && (!isFirstMove))
                {
                    pos.Play(m);
                    returnCode = NegaScout(ref score, ref pos, ref pv, -b, -alpha, depth + 1, maxDepth);
                    pos.Unplay(m);
                    if (returnCode != ReturnCode.OK)
                        return returnCode;
                    alpha = Math.Max(alpha, score);
                    if (alpha >= beta)
                    {
                        score = alpha;
                        return ReturnCode.OK;
                    }
                    b = alpha + 1;
                }
                
                isFirstMove = false;
             }
            score = alpha;
            return ReturnCode.OK;
        }

        
        // A try for the iterative version
        private ReturnCode AlphaBetaIterative(ref int score, ref Position position, ref Stack<Move> pv, int alpha, int beta, int depth, int maxDepth)
        {
            // create a copy free to be left draft if the calculation is not complete
            Position pos = new Position(ref position);

            List<Move> moves = new List<Move>();
            const int STACKOFFSET = 2;
            int L = maxDepth;
            // alpha,beta will not be used (only for compatibility)
            int l; // level of recursion
            int[] a = new int[L + STACKOFFSET]; // stack for recusrsion where a[l-2],a[l-1],a[l],a[l+1] denote respectively alpha, -beta, m, -t in procedure F2
            IterativePosStackItem[] r = new IterativePosStackItem[L + 1]; // another stack of recursion where r[l] and r[l+1] denotes respectively p and q in F2
            l = 0;
            a[0] = a[1] = -VALUE_INFINITE;
            r[0] = new IterativePosStackItem(pos);
            
        F2:
            // quick exit
            if (brainStatus != BrainStatus.THINKING)
                return ReturnCode.STOPTHINKING;

            //moves.Clear(); //GetLegalMoves(ref r[l].position, moves);
            //r[l + 1] = first(r[l]);
            if (IsCheck(ref pos))
            {

                goto done;
            }

            r[l + 1] = new IterativePosStackItem(pos);
            
            //if(r[l+1]==V) 
            if (r[l + 1].End() && Engine.IsCheck(ref pos)) 
                {
                    //pos.Unplay(r[l + 1].GetMove()); // undo before l--
                    a[l + STACKOFFSET] = VALUE_MATE - 1 - l; // + or - with -l offset
                    goto done;
                }
            if (((l + 1) >= L) || r[l + 1].End()) 
            {
                //pos.Unplay(r[l].GetMove()); // undo before l--
                // eval of r(l)
                a[l + STACKOFFSET] = Engine.EvaluateAbsolute(pos);
                goto done;
            }
            // begin
            pos.Play(r[l + 1].GetMove());

            a[l + STACKOFFSET] = a[l];
        loop:
            l++; goto F2;
        resume:
            if (-a[l + 1 + STACKOFFSET] > a[l + STACKOFFSET])
            // begin
            {
                a[l + STACKOFFSET] = -a[l + 1 + STACKOFFSET];
                if (a[l + 1 + STACKOFFSET] <= a[l - 1 + STACKOFFSET])
                {
                    //pos.Unplay(r[l].GetMove()); // undo before l--
                    goto done;
                }
            }// end
            //r[l + 1] = next(r[l + 1]);
            //pos.Unplay(r[l + 1].GetMove());
            r[l + 1].Next();
            //if (r[l + 1] != V)
            if (!r[l + 1].End())
            {
                //pos.Unplay(r[l+1].GetMove());
                goto loop;
            }

        done:
            //pos.Unplay(r[l + 1].GetMove());
            pos.Unplay(r[l].GetMove());
            
            l--;
            if (l >= 0)
                goto resume;
            score = a[0 + STACKOFFSET];

            return ReturnCode.OK;
        }
        

        /*
         * Stop the main injector loop
         * 
         */ 
        public void Stop()
        {
            brainStatus = BrainStatus.PAUSED;
            watch.Reset();
            isSearchMove = false;
        }

        /*
         * Start the main injector loop
         * 
         */ 
        public void Start()
        {
            watch.Start();
            // Must be done before each Search (this the corresp. function)
            //TT.Clear();
            nbProcessedNodes = 0;
            if (!isSearchMove)
            {
                moves.Clear();
                // New alphabeta implementation
                GetLegalMoves(ref currentPosition, ref moves);
            } // else moves are already provided

            //DisplayMoves(moves);

            watch.Start();
            // reajust thinking time
            if (brainMode == BrainMode.ADJUSTTIME_MODE)
                UpdateThinkDelay();


            brainStatus = BrainStatus.THINKING;
        }

        private void DisplayMoves(List<Move> moves)
        {
            StringBuilder sb = new StringBuilder();
            sb.Append("info #### MOVES TO EVALUATE (");
            sb.Append(moves.Count);
            sb.Append(")");

            foreach (Move m in moves)
                sb.Append(m.ToString() + " ");
            Console.WriteLine(sb.ToString());
        }

        public void SetDebug(bool isDebugOn)
        {
            debugMode = isDebugOn;
        }

        public void SetOption(String name, String value)
        {
            switch(name)
            {
                    /*
                // Simplification => param names without spaces
                case "PawnValue":
                    this.SetPawnValue(Int32.Parse(value));
                    break;
                case "KnightValue":
                    this.SetKnightValue(Int32.Parse(value));
                    break;
                case "BishopValue":
                    this.SetBishopValue(Int32.Parse(value));
                    break;
                case "RookValue":
                    this.SetRookValue(Int32.Parse(value));
                    break;
                case "QueenValue":
                    this.SetRookValue(Int32.Parse(value));
                    break;
                     * */
                case "Smart Timing":
                    this.SetSmartTiming(value == "on");
                    break;
                default:
                    System.Console.WriteLine("Unknown option: " + name);
                    break;
            }
        }

        private void SetSmartTiming(bool value)
        {
            isSmartTiming = value;
        }


        /**
         * Evaluate the score of the currentPosition used by the Alpha-Beta
         * algorithm
         * 
         * @param currentPosition
         * @return
         */
        public static int EvaluateRelative(Position position, int turn)
        {
            // TODO: improve the evaluation method
            // SIDE RELATIVE EVAL FUNCTION
            //materialScore = kingWt  * (wK-bK)
            //              + queenWt * (wQ-bQ)
            //              + rookWt  * (wR-bR)
            //              + knightWt* (wN-bN)
            //              + bishopWt* (wB-bB)
            //              + pawnWt  * (wP-bP)
            //mobilityScore = mobilityWt * (wMobility-bMobility)
            //Eval  = (materialScore + mobilityScore) * who2Move


            // Part 1 - Basic evaluation : just count the pieces for ech side with coefs
            int staticEval = 0; 
            if (turn==WHITE) staticEval = position.Evaluate(ref W_coeff);
            else staticEval = position.Evaluate(ref B_coeff);

            // Part 2 - Attack factor = how many captures are possible from this position
            // max attack factor 
            /*
            int attackMaxValue = turn ? W_coeff[0] : B_coeff[0];
            int attackOffset = (int)(attackMaxValue*AttackFactor(ref position));

            // Part 3 - Positionnal score : the delta score which can make
            //          the difference between to positions with the same score
            //          Note: this delta-score should be a [-100cp;100cp] value maximum
            // TODO: implement this part with the use of Bitboards
            */
            return staticEval /*+ attackOffset*/;
        }

        public static int EvaluateAbsolute(Position position)
        {
            // TODO: improve the evaluation method with bitboards
            // SHANNON'S EVAL FUNCTION
            //f(p) = 200(K-K')
            //       + 9(Q-Q')
            //       + 5(R-R')
            //       + 3(B-B' + N-N')
            //       + 1(P-P')
            //       - 0.5(D-D' + S-S' + I-I')
            //       + 0.1(M-M') + ...
            //KQRBNP = number of kings, queens, rooks, bishops, knights and pawns
            //D,S,I = doubled, blocked and isolated pawns
            //M = Mobility (the number of legal moves)
            int staticEval = position.Evaluate(ref coeff);

            return staticEval;
        }

        private static float AttackFactor(ref Position position)
        {
            List<Move> moves = new List<Move>();
            GetLegalMoves(ref position, ref moves);
            if (moves.Count == 0)
                return 0;
            int attackCount = 0;

            foreach (Move m in moves)
            {
                if (m.IsCapture())
                    attackCount++;
            }

            return attackCount / moves.Count;
        }



        //
        // Get the pieces left on the currentPosition
        //
        private static int[] GetPiecesLeft(ref Position position)
        {
            int[] nbpieces = new int[12];
            Piece piece = Piece.NO_PIECE;
            for (int i = 0; i < 12; i++)
            {
                nbpieces[i] = 0;
            }
            for (int i = 0; i < 64; i++)
            {
                piece = position.GetPiece(i);
                if (piece != Piece.NO_PIECE)
                {
                    nbpieces[(int)piece]++;
                }
            }

            return nbpieces;
        }

        //
        // Give the list of possible legal moves
        //
        public static void GetPseudoLegalMoves(ref Position position, ref List<Move> moves)
        {
            moves.Clear();
            for (int square = 0; square < 64; square++)
            {
                if (!position.IsEmptyOrOpponent(square))
                {
                    GetPseudoLegalMoves(ref position, square, moves);
                }
            }
        }

        public static bool IsCheck(ref Position position)
        {
            // new bitboard implementation
            return position.IsCheck(position.GetTurn()==WHITE ? 0 : 1);
            // old implementation
            //return IsCheck(ref position, position.GetTurn());
        }

        /**
         * Indicate if the currentPosition is check
         * for the given player
         * @param currentPosition
         * @return
         */
        // bitboard version
        public static bool IsCheck(ref Position position, int bySide)
        {

            return position.IsCheck(bySide);
        }
        
        public static bool IsCheck(ref Position position, bool playerColor)
        {
            //TODO: modify return block to take chessmen power/given check frequency into account
            Piece king = playerColor ? Piece.W_KING : Piece.B_KING;
            Piece oKing = playerColor ? Piece.B_KING : Piece.W_KING;
            Piece oQueen = playerColor ? Piece.B_QUEEN : Piece.W_QUEEN;
            Piece oRook = playerColor ? Piece.B_ROOK : Piece.W_ROOK;
            Piece oBish = playerColor ? Piece.B_BISHOP : Piece.W_BISHOP;
            Piece oKnig = playerColor ? Piece.B_KNIGHT : Piece.W_KNIGHT;
            Piece oPawn = playerColor ? Piece.B_PAWN : Piece.W_PAWN;
            bool oColor = !playerColor;

            // get king square
            int square;
            for (square = 0; square < 64; square++)
                if (position.GetPiece(square) == king)
                    break;
            Debug.Assert((square >= Square.SQ_A1) && (square <= Square.SQ_H8));

            int col = Square.GetCol(square);
            int row = Square.GetRow(square);


            // king threat (virtual)
            if (col > 0)
                if (position.GetPiece(square - 1) == oKing)
                    return true;
            if (col > 0 && row < 7)
                if (position.GetPiece(square + 7) == oKing)
                    return true;
            if (row < 7)
                if (position.GetPiece(square + 8) == oKing)
                    return true;
            if (col < 7 && row < 7)
                if (position.GetPiece(square + 9) == oKing)
                    return true;
            if (col < 7)
                if (position.GetPiece(square + 1) == oKing)
                    return true;
            if (col < 7 && row > 0)
                if (position.GetPiece(square - 7) == oKing)
                    return true;
            if (row > 0)
                if (position.GetPiece(square - 8) == oKing)
                    return true;
            if (col > 0 && row > 0)
                if (position.GetPiece(square - 9) == oKing)
                    return true;

            // Pawn threat
            if (playerColor)
            {
                if (col > 0 && row < 7)
                    if (position.GetPiece(square + 7) == oPawn)
                        return true;
                if (col < 7 && row < 7)
                    if (position.GetPiece(square + 9) == oPawn)
                        return true;
            }
            else
            {
                if (col > 0 && row > 0)
                    if (position.GetPiece(square - 9) == oPawn)
                        return true;
                if (col < 7 && row > 0)
                    if (position.GetPiece(square - 7) == oPawn)
                        return true;
            }

            // Knight threat
            if (col > 0 && row < 6 && position.IsEmptyOrColor(square + 15, oColor))
                if (position.GetPiece(square + 15) == oKnig)
                    return true;
            if (col < 7 && row < 6 && position.IsEmptyOrColor(square + 17, oColor))
                if (position.GetPiece(square + 17) == oKnig)
                    return true;
            if (col < 6 && row < 7 && position.IsEmptyOrColor(square + 10, oColor))
                if (position.GetPiece(square + 10) == oKnig)
                    return true;
            if (col < 6 && row > 0 && position.IsEmptyOrColor(square - 6, oColor))
                if (position.GetPiece(square - 6) == oKnig)
                    return true;
            if (col < 7 && row > 1 && position.IsEmptyOrColor(square - 15, oColor))
                if (position.GetPiece(square - 15) == oKnig)
                    return true;
            if (col > 0 && row > 1 && position.IsEmptyOrColor(square - 17, oColor))
                if (position.GetPiece(square - 17) == oKnig)
                    return true;
            if (col > 1 && row > 0 && position.IsEmptyOrColor(square - 10, oColor))
                if (position.GetPiece(square - 10) == oKnig)
                    return true;
            if (col > 1 && row < 7 && position.IsEmptyOrColor(square + 6, oColor))
                if (position.GetPiece(square + 6) == oKnig)
                    return true;


            // bishop&queen threat
            // Up-right moves
            int sqStart = square + 9;
            int sqEnd = Math.Min(64, square + 9 * (8 - col));
            for (int sq = sqStart; sq < sqEnd; sq += 9)
            {
                if (position.IsEmptyOrColor(sq, oColor))
                {
                    Piece p = position.GetPiece(sq);
                    if ((p == oBish) || (p == oQueen))
                        return true;
                    if (p != Piece.NO_PIECE)
                        break;
                }
                else break;
            }

            // Down-right moves
            sqStart = square - 7;
            sqEnd = Math.Max(-1, square - 7 * (8 - col));
            for (int sq = sqStart; sq > sqEnd; sq -= 7)
            {
                if (position.IsEmptyOrColor(sq, oColor))
                {
                    Piece p = position.GetPiece(sq);
                    if ((p == oBish) || (p == oQueen))
                        return true;
                    if (p != Piece.NO_PIECE)
                        break;
                }
                else break;
            }

            // Down-left moves
            sqStart = square - 9;
            sqEnd = Math.Max(-1, square - 9 * (col + 1));
            for (int sq = sqStart; sq > sqEnd; sq -= 9)
            {
                if (position.IsEmptyOrColor(sq, oColor))
                {
                    Piece p = position.GetPiece(sq);
                    if ((p == oBish) || (p == oQueen))
                        return true;
                    if (p != Piece.NO_PIECE)
                        break;
                }
                else break;
            }
            // Up-left moves
            sqStart = square + 7;
            sqEnd = Math.Min(64, square + 7 * (col + 1));
            for (int sq = sqStart; sq < sqEnd; sq += 7)
            {
                if (position.IsEmptyOrColor(sq, oColor))
                {
                    Piece p = position.GetPiece(sq);
                    if ((p == oBish) || (p == oQueen))
                        return true;
                    if (p != Piece.NO_PIECE)
                        break;
                }
                else break;
            }


            // rook&queen threat
            // Horizontal moves right
            sqStart = square + 1;
            sqEnd = 8 * (row + 1);
            for (int sq = sqStart; sq < sqEnd; sq++)
            {
                if (position.IsEmptyOrColor(sq, oColor))
                {
                    Piece p = position.GetPiece(sq);
                    if ((p == oRook) || (p == oQueen))
                        return true;
                    if (p != Piece.NO_PIECE)
                        break;
                }
                else break;
            }

            // Horizontal moves left
            sqStart = square - 1;
            sqEnd = 8 * row - 1;
            for (int sq = sqStart; sq > sqEnd; sq--)
            {
                if (position.IsEmptyOrColor(sq, oColor))
                {
                    Piece p = position.GetPiece(sq);
                    if ((p == oRook) || (p == oQueen))
                        return true;
                    if (p != Piece.NO_PIECE)
                        break;
                }
                else break;
            }

            // Vertical moves up
            sqStart = square + 8;
            sqEnd = 64;
            for (int sq = sqStart; sq < sqEnd; sq+=8)
            {
                if (position.IsEmptyOrColor(sq, oColor))
                {
                    Piece p = position.GetPiece(sq);
                    if ((p == oRook) || (p == oQueen))
                        return true;
                    if (p != Piece.NO_PIECE)
                        break;
                }
                else break;
            }
            // Vertical moves down
            sqStart = square - 8;
            sqEnd = -1;
            for (int sq = sqStart; sq > sqEnd; sq-=8)
            {
                if (position.IsEmptyOrColor(sq, oColor))
                {
                    Piece p = position.GetPiece(sq);
                    if ((p == oRook) || (p == oQueen))
                        return true;
                    if (p != Piece.NO_PIECE)
                        break;
                }
                else break;
            }

            return false;

        }


        /**
         * Get the possible moves for one piece
         * 
         * @param currentPosition
         * @param square
         * @return
         */
        private static void GetPseudoLegalMoves(ref Position position, int square, List<Move> possibleMoves)
        {
            Piece pieceCode = position.GetPiece(square);

            if ((position.IsBlackToMove() && position.IsPieceBlack(pieceCode))
                    || (position.IsWhiteToMove() && position.IsPieceWhite(pieceCode)))
            {

                switch (pieceCode)
                {
                    case Piece.W_PAWN:
                    case Piece.B_PAWN:
                        GetPossiblePawnMoves(ref position, square, possibleMoves);
                        break;
                    case Piece.W_BISHOP:
                    case Piece.B_BISHOP:
                        GetPossibleBishopMoves(ref position, square, possibleMoves);
                        break;
                    case Piece.W_KNIGHT:
                    case Piece.B_KNIGHT:
                        GetPossibleKnightMoves(ref position, square, possibleMoves);
                        break;
                    case Piece.W_ROOK:
                    case Piece.B_ROOK:
                        GetPossibleRookMoves(ref position, square, possibleMoves);
                        break;
                    case Piece.W_QUEEN:
                    case Piece.B_QUEEN:
                        GetPossibleQueenMoves(ref position, square, possibleMoves);
                        break;
                    case Piece.W_KING:
                    case Piece.B_KING:
                        GetPossibleKingMoves(ref position, square, possibleMoves);
                        break;
                    default:
                        break;

                }
            }
        }

        /**
         * Get possible moves for King
         * 
         * @param currentPosition
         * @param square
         * @return
         */
        private static void GetPossibleKingMoves(ref Position position, int square, List<Move> possibleKingMoves)
        {
            int col = Square.GetCol(square);
            int row = Square.GetRow(square);

            if (col < 7 && position.IsEmptyOrOpponent(square+1))
            {
                Move move = new Move(square, square+1,position);
                possibleKingMoves.Add(move);
            }
            if (col < 7 && row < 7 && position.IsEmptyOrOpponent(square+9))
            {
                Move move = new Move(square, square+9,position);
                possibleKingMoves.Add(move);
            }
            if (row < 7 && position.IsEmptyOrOpponent(square+8))
            {
                Move move = new Move(square, square+8,position);
                possibleKingMoves.Add(move);
            }
            if (col > 0 && row < 7 && position.IsEmptyOrOpponent(square+7))
            {
                Move move = new Move(square, square+7,position);
                possibleKingMoves.Add(move);
            }
            if (col > 0 && position.IsEmptyOrOpponent(square-1))
            {
                Move move = new Move(square, square-1,position);
                possibleKingMoves.Add(move);
            }
            if (col > 0 && row > 0 && position.IsEmptyOrOpponent(square-9))
            {
                Move move = new Move(square, square-9,position);
                possibleKingMoves.Add(move);
            }
            if (row > 0 && position.IsEmptyOrOpponent(square-8))
            {
                Move move = new Move(square, square -8,position);
                possibleKingMoves.Add(move);
            }
            if (col < 7 && row > 0 && position.IsEmptyOrOpponent(square-7))
            {
                Move move = new Move(square, square-7,position);
                possibleKingMoves.Add(move);
            }

            if (position.GetTurn()==WHITE)
            {
                if (position.WhiteCanCastleQueenSide()
                    && position.GetPiece(Square.SQ_B1) == Piece.NO_PIECE
                    && position.GetPiece(Square.SQ_C1) == Piece.NO_PIECE
                    && position.GetPiece(Square.SQ_D1) == Piece.NO_PIECE
                    )
                {
                    Move subMove = new Move(Square.SQ_E1, Square.SQ_D1,position);
                    position.Play(subMove);
                    bool notCheck = !IsCheck(ref position);
                    position.Unplay(subMove);
                    if (notCheck)
                    {
                        possibleKingMoves.Add(new Move(Square.SQ_E1, Square.SQ_C1, position));
                    } 
                }
                if (position.WhiteCanCastleKingSide()
                        && position.GetPiece(Square.SQ_E1) == Piece.NO_PIECE
                        && position.GetPiece(Square.SQ_F1) == Piece.NO_PIECE)
                {
                    Move subMove = new Move(Square.SQ_E1, Square.SQ_F1,position);
                    position.Play(subMove);
                    bool notCheck = !IsCheck(ref position);
                    position.Unplay(subMove);
                    if (notCheck)
                    {
                        possibleKingMoves.Add(new Move(Square.SQ_E1, Square.SQ_G1, position));
                    }
                }
            } else
            {
                if (position.BlackCanCastleQueenSide()
                    && position.GetPiece(Square.SQ_B8) == Piece.NO_PIECE
                    && position.GetPiece(Square.SQ_C8) == Piece.NO_PIECE
                    && position.GetPiece(Square.SQ_D8) == Piece.NO_PIECE
                    )
                {
                    Move subMove = new Move(Square.SQ_E8, Square.SQ_D8,position);
                    position.Play(subMove);
                    bool notCheck = !IsCheck(ref position);
                    position.Unplay(subMove);
                    if (notCheck)
                    {
                        possibleKingMoves.Add(new Move(Square.SQ_E8, Square.SQ_C8,position));
                    }
                }
                if (position.BlackCanCastleKingSide()
                        && position.GetPiece(Square.SQ_E8) == Piece.NO_PIECE
                        && position.GetPiece(Square.SQ_F8) == Piece.NO_PIECE)
                {
                    Move subMove = new Move(Square.SQ_E8, Square.SQ_F8, position);
                    position.Play(subMove);
                    bool notCheck = !IsCheck(ref position);
                    position.Unplay(subMove);
                    if (notCheck)
                    {
                        possibleKingMoves.Add(new Move(Square.SQ_E8, Square.SQ_G8, position));
                    }
                }
            }
        }

        /**
         * Get possible moves for Queen
         * 
         * @param currentPosition
         * @param square
         * @return
         */
        private static void GetPossibleQueenMoves(ref Position position, int square, List<Move> possibleQueenMoves)
        {
            GetPossibleRookMoves(ref position, square, possibleQueenMoves);
            GetPossibleBishopMoves(ref position, square, possibleQueenMoves);
        }

        /*
         * Get possible moves for Rook
         */
        private static void GetPossibleRookMoves(ref Position position, int square, List<Move> possibleRookMoves)
        {
            int col = Square.GetCol(square);
            int row = Square.GetRow(square);

            // Horizontal moves right
            int sqStart = square + 1;
            int sqEnd = 8 * (row+1);
            for (int sq = sqStart; sq < sqEnd; sq++)
            {
                if (position.IsEmptyOrOpponent(sq))
                {
                    Move move = new Move(square, sq, position);
                    possibleRookMoves.Add(move);
                    if (!position.IsSquareEmpty(sq))
                        break;
                }
                else
                    break;
            }

            // Horizontal moves left
            sqStart = square - 1;
            sqEnd = 8 * row - 1;
            for (int sq = sqStart; sq > sqEnd; sq--)
            {
                if (position.IsEmptyOrOpponent(sq))
                {
                    Move move = new Move(square, sq, position);
                    possibleRookMoves.Add(move);
                    if (!position.IsSquareEmpty(sq))
                        break;
                }
                else
                    break;
            }


            // Vertical moves up
            sqStart = square + 8;
            sqEnd = 64;
            for (int sq = sqStart; sq < sqEnd; sq+=8)
            {
                if (position.IsEmptyOrOpponent(sq))
                {
                    Move move = new Move(square, sq, position);
                    possibleRookMoves.Add(move);
                    if (!position.IsSquareEmpty(sq))
                        break;
                }
                else
                    break;
            }

            // Vertical moves down
            sqStart = square - 8;
            sqEnd = -1;
            for (int sq = sqStart; sq > sqEnd; sq-=8)
            {
                if (position.IsEmptyOrOpponent(sq))
                {
                    Move move = new Move(square, sq, position);
                    possibleRookMoves.Add(move);
                    if (!position.IsSquareEmpty(sq))
                        break;
                }
                else
                    break;
            }
        }

        /**
         * Get possible moves for Knight
         * 
         * @param currentPosition
         * @param square
         * @return
         */
        private static void GetPossibleKnightMoves(ref Position position, int square, List<Move> possibleKnightMoves)
        {
            //List<Move> possibleKnightMoves = new List<Move>();
            int col = Square.GetCol(square);
            int row = Square.GetRow(square);

            if (col > 0 && row < 6 && position.IsEmptyOrOpponent(square+15))
            {
                Move move = new Move(square, square+15,position);
                possibleKnightMoves.Add(move);
            }
            if (col < 7 && row < 6 && position.IsEmptyOrOpponent(square+17))
            {
                Move move = new Move(square, square+17,position);
                possibleKnightMoves.Add(move);
            }
            if (col < 6 && row < 7 && position.IsEmptyOrOpponent(square+10))
            {
                Move move = new Move(square, square+10,position);
                possibleKnightMoves.Add(move);
            }
            if (col < 6 && row > 0 && position.IsEmptyOrOpponent(square-6))
            {
                Move move = new Move(square, square-6,position);
                possibleKnightMoves.Add(move);
            }
            if (col < 7 && row > 1 && position.IsEmptyOrOpponent(square-15))
            {
                Move move = new Move(square, square - 15, position);
                possibleKnightMoves.Add(move);
            }
            if (col > 0 && row > 1 && position.IsEmptyOrOpponent(square - 17))
            {
                Move move = new Move(square, square - 17, position);
                possibleKnightMoves.Add(move);
            }
            if (col > 1 && row > 0  && position.IsEmptyOrOpponent(square-10))
            {
                Move move = new Move(square, square - 10, position);
                possibleKnightMoves.Add(move);
            }
            if (col > 1 && row < 7 && position.IsEmptyOrOpponent(square+6))
            {
                Move move = new Move(square, square + 6, position);
                possibleKnightMoves.Add(move);
            }
        }

        /**
         * Get possible moves for Bishop
         * 
         * @param currentPosition
         * @param square
         * @return
         */
        private static void GetPossibleBishopMoves(ref Position position, int square, List<Move> possibleBishopMoves)
        {
            //List<Move> possibleBishopMoves = new List<Move>();
            int col = Square.GetCol(square);
            int row = Square.GetRow(square);

            // Up-right moves
            int sqStart = square + 9;
            int sqEnd = Math.Min(64, square + 9 * (8 - col));
            for (int sq = sqStart; sq < sqEnd; sq += 9)
            {
                if (position.IsEmptyOrOpponent(sq))
                {
                    Move move = new Move(square, sq, position);
                    possibleBishopMoves.Add(move);
                    if (!position.IsSquareEmpty(sq)) 
                        break;
                }
                else 
                    break;
            }

            // Down-right moves
            sqStart = square - 7;
            sqEnd = Math.Max(-1, square - 7 * (8 - col));
            for (int sq = sqStart; sq > sqEnd ; sq -= 7)
            {
                if (position.IsEmptyOrOpponent(sq))
                {
                    Move move = new Move(square, sq, position);
                    possibleBishopMoves.Add(move);
                    if (!position.IsSquareEmpty(sq)) 
                        break;
                }
                else 
                    break;
            }

            // Down-left moves
            sqStart = square - 9;
            sqEnd = Math.Max(-1, square - 9 * (col + 1));
            for (int sq = sqStart ; sq > sqEnd; sq -= 9)
            {
                if (position.IsEmptyOrOpponent(sq))
                {
                    Move move = new Move(square, sq, position);
                    possibleBishopMoves.Add(move);
                    if (!position.IsSquareEmpty(sq))
                        break;
                }
                else 
                    break;
            }
            // Up-left moves
            sqStart = square + 7;
            sqEnd = Math.Min(64, square + 7 * (col + 1));
            for (int sq = sqStart; sq < sqEnd; sq += 7)
            {
                if (position.IsEmptyOrOpponent(sq))
                {
                    Move move = new Move(square, sq, position);
                    possibleBishopMoves.Add(move);
                    if (!position.IsSquareEmpty(sq))
                        break;
                }
                else
                    break;
            }
        }

        /**
         * Get possible moves for Pawn
         * 
         * @param currentPosition
         * @param square
         * @return
         */
        private static void GetPossiblePawnMoves(ref Position position, int square, List<Move> possiblePawnMoves)
        {
            List<Move> pawnMoves = new List<Move>();
            Piece piece = position.GetPiece(square);
            int col = Square.GetCol(square);
            int row = Square.GetRow(square);
            
            if (piece == Piece.W_PAWN && row < 7)
            {
                // Pawn's move
                //if (position.GetPiece(Square.Get(col, row + 1)) == Piece.EMPTY)
                if (position.GetPiece(square+8) == Piece.NO_PIECE)
                {
                    //Move move = new Move(square, Square.Get(col, row + 1));
                    Move move = new Move(square, square + 8, position);
                    pawnMoves.Add(move);
                }
                //if (row == 1 && (position.GetPiece(Square.Get(col, row + 1)) == Piece.EMPTY) && (position.GetPiece(Square.Get(col, row + 2)) == Piece.EMPTY))
                if (row == 1 && (position.GetPiece(square+8) == Piece.NO_PIECE) && (position.GetPiece(square+16) == Piece.NO_PIECE))
                {
                    //Move move = new Move(square, Square.Get(col, row + 2));
                    Move move = new Move(square, square + 16, position);
                    pawnMoves.Add(move);
                }
                // Pawn capture
                //if (col < 7 && position.IsPieceBlack(position.GetPiece(Square.Get(col + 1, row + 1))))
                if (col < 7 && (position.IsPieceBlack(position.GetPiece(square+9)) || (position.LastEnPassant() == (square+9))))
                {
                    //Move move = new Move(square, Square.Get(col + 1, row + 1));
                    Move move = new Move(square, square + 9, position);
                    pawnMoves.Add(move);
                }
                //if (col > 0 && position.IsPieceBlack(position.GetPiece(Square.Get(col - 1, row + 1))))
                if (col > 0 && (position.IsPieceBlack(position.GetPiece(square+7))|| (position.LastEnPassant() == (square+7))))
                {
                    //Move move = new Move(square, Square.Get(col - 1, row + 1));
                    Move move = new Move(square, square + 7, position);
                    pawnMoves.Add(move);
                }
                // TODO implement "en passant"

            }
            if (piece == Piece.B_PAWN && row > 0)
            {
                // Pawn's move
                //if (position.GetPiece(Square.Get(col, row - 1)) == Piece.EMPTY)
                if (position.GetPiece(square-8) == Piece.NO_PIECE)
                {
                    //Move move = new Move(square, Square.Get(col, row - 1));
                    Move move = new Move(square, square - 8, position);
                    pawnMoves.Add(move);
                }
                //if (row == 6 && (position.GetPiece(Square.Get(col, row - 1)) == Piece.EMPTY) && (position.GetPiece(Square.Get(col, row - 2)) == Piece.EMPTY))
                if (row == 6 && (position.GetPiece(square - 8) == Piece.NO_PIECE) && (position.GetPiece(square - 16) == Piece.NO_PIECE))
                   
                {
                    //Move move = new Move(square, Square.Get(col, row - 2));
                    Move move = new Move(square, square - 16, position);
                    pawnMoves.Add(move);

                }
                // Pawn capture
                // Pawn capture
                if (col < 7 && (position.IsPieceWhite(position.GetPiece(square - 7)) || (position.LastEnPassant() == (square - 7))))
                {
                    Move move = new Move(square, square - 7, position);
                    pawnMoves.Add(move);
                }
                if (col > 0 && (position.IsPieceWhite(position.GetPiece(square - 9)) || (position.LastEnPassant() == (square - 9))))
                {
                    Move move = new Move(square, square - 9, position);
                    pawnMoves.Add(move);
                }
            }

            // adding alternate promotions
            foreach (Move m in pawnMoves)
            {
                int r = Square.GetRow(m.to);
                if (m.promotion == '0' && (r == 0 || r == 7))
                {
                    possiblePawnMoves.Add(new Move(m.from, m.to, position, 'q'));
                    possiblePawnMoves.Add(new Move(m.from, m.to, position, 'r'));
                    possiblePawnMoves.Add(new Move(m.from, m.to, position, 'b'));
                    possiblePawnMoves.Add(new Move(m.from, m.to, position, 'n'));
                }
                else
                {
                    possiblePawnMoves.Add(m);
                }
            }
            
        }

        /**
         * Get legal moves
         * @param currentPosition
         * @return
         */
        public static int GetLegalMoves(ref Position pos, ref List<Move> legalMoves)
        {
            legalMoves.Clear();
            if (IsFiftyMovesDraw(ref pos) || IsThreeTimesRepetitionDraw(ref pos))
                return 0;
            List<Move> possibleMoves = new List<Move>();
            GetPseudoLegalMoves(ref pos, ref possibleMoves);
            int turn = pos.GetTurn();
            foreach (Move m in possibleMoves)
            {
                pos.Play(m);
                // new bitboard implementation
                if(!pos.IsCheck(turn))
                // old implementation
                //if (!IsCheck(ref pos,turn))
                {
                    legalMoves.Add(m);
                }
                pos.Unplay(m);
            }
            // could be done at insert
            // uses the Move sort CompareTo(Obj obj)
            // in order to boost alphabeta pruning
            legalMoves.Sort();
            return legalMoves.Count;
        }

        public static bool IsThreeTimesRepetitionDraw(ref Position pos)
        {
            // the position cannot be identical if the 50 moves clock is lower than 6 half plies
            if (pos.GetMovesWithoutCaptureOrPawnPush() < 6 
                || pos.GetPlayedMoveNumber() < 6)
                return false;
            
            return pos.IsThreeTimesRepetitionDraw();
        }

        public static bool IsFiftyMovesDraw(ref Position pos)
        {
            return (pos.GetMovesWithoutCaptureOrPawnPush() >= 50);
        }

 
        public Move? GetBestMove()
        {
            return bestMove;
        }


        public void SetDepthLevel(int depth)
        {
            this.depthLevel = depth;
        }

        public void SetTimeLevel(int timeLevel)
        {
            brainMode = BrainMode.MOVETIME_MODE;
            this.thinkDelay = timeLevel;
        }
        
        public void SetStartPosition()
        {
            SetPosition("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
        }

        public void SetPosition(string strPos)
        {
            currentPosition = new Position(strPos);
        }

        public void Ponderhit()
        {
            throw new NotImplementedException();
        }

        public void SetSearchmovesMode(List<Move> selectedMoves)
        {
            // don't forget to switch to false once used
            this.moves = selectedMoves;
            isSearchMove = true;
        }

        public void SetPonderMode()
        {
            throw new NotImplementedException();
        }

        public void SetWtime(int timeLeft)
        {
            this.wtime = new TimeSpan(0, 0, 0, 0, timeLeft);
            this.brainMode = BrainMode.ADJUSTTIME_MODE;
        }

        public void SetBtime(int timeLeft)
        {
            this.btime = new TimeSpan(0, 0, 0, 0, timeLeft);
            this.brainMode = BrainMode.ADJUSTTIME_MODE;
        }

        public void SetWinc(int increment)
        {
            this.winc = new TimeSpan(0,0,0,0,increment);
            this.brainMode = BrainMode.ADJUSTTIME_MODE;
        }

        public void SetBinc(int increment)
        {
            this.binc = new TimeSpan(0, 0, 0, 0, increment);
            this.brainMode = BrainMode.ADJUSTTIME_MODE;
        }

        public void SetMovestogo(int movesUntilNextTimeControl)
        {
            throw new NotImplementedException();
        }

        public void SetDepthMode(int pliesDepth)
        {
            brainMode = BrainMode.DEPTH_MODE;
            depthLevel = pliesDepth; 
        }

        public void SetNodesMode(int nodesDepth)
        {
            brainMode = BrainMode.NODES_MODE;
            this.nodeMaxNumber = nodesDepth;
        }

        public void SetMateMode(int mateDepth)
        {
            brainMode = BrainMode.MATE_MODE;
            depthLevel = mateDepth;
        }

        public void SetMovetimeMode(int searchTime)
        {
            this.thinkDelay = searchTime;
            brainMode = BrainMode.MOVETIME_MODE;
        }

        public void SetInfiniteMode()
        {
            brainMode = BrainMode.INFINITE_MODE;
        }

        public void SetVerboseMode(bool isVerboseMode)
        {
            isVerbose = isVerboseMode;
        }

        private void UpdateThinkDelay()
        {
            int playerInc = 0;
            int playerTime = 0;
            int oppInc = 0;
            int oppTime = 0;
            if (currentTurn == WHITE)
            {
                playerInc = (int)winc.TotalMilliseconds;
                playerTime = (int)wtime.TotalMilliseconds;
                oppInc = (int)binc.TotalMilliseconds;
                oppTime = (int)btime.TotalMilliseconds;
            } else {
                playerInc = (int)this.binc.TotalMilliseconds;
                playerTime = (int)btime.TotalMilliseconds;
                oppInc = (int)winc.TotalMilliseconds;
                oppTime = (int)wtime.TotalMilliseconds;
            }
            int delay;
            int extraDelay;
            // Smart timing : the engine adjust its think time depending on 
            // the time left for itself and the opponent
            // TODO: improve calculation
            // TODO: link calculation to current nodeStack/score state
            if (isSmartTiming)
            {
                if (playerInc == 0)
                {
                    // TODO: improve time calculation when there is no inc

                    // no increment
                    // time must be managed carefully
                    if (currentTurn == WHITE)
                    {
                        // White to play
                        if (playerTime > oppTime)
                        {
                            delay = (int)Math.Max(playerInc, playerTime / 20);
                        }
                        else
                        {
                            delay = (int)Math.Max(playerInc, playerTime / 20);
                        }


                    }
                    else
                    {
                        // Black to play
                        // they can decide how much time to spend depending on whites clock
                        if (playerTime > oppTime)
                        {
                            delay = (int)Math.Max(playerInc, playerTime / 20);
                        }
                        else
                        {
                            delay = (int)Math.Max(playerInc, playerTime / 20);
                        }

                    }


                }
                else
                {
                    // base time
                    delay = playerInc;

                    // extra time taken from the clock
                    if(playerTime<10000){
                        // for timer < 10s try to save some time
                        extraDelay = playerTime*60/100;
                    }
                    else{
                        extraDelay = Math.Max(playerTime/Math.Min(40,Math.Max(5,Math.Abs(40-currentPosition.GetPlayedMoveNumber()))),8000);
                    }
                    delay += extraDelay;
                }

            } 
            else
                // NO SMART TIMING
            {
                delay = (int)Math.Max(playerInc, playerTime / 20);
            }


            thinkDelay = delay;
            System.Console.WriteLine("Think delay updated : " + thinkDelay );
        }

        /*
        public void DisplayBestPv(int maxDepth) {

            if (possibleNodes.Count > 0) {
                //SortLegalMoves();

                int depth = 1;
                Node bestNode = GetBestNode();
                Console.WriteLine("info currmove " + bestNode.GetPreviousMove());

                long time = watch.ElapsedMilliseconds;
                int nodeNb = nodeQueue.Count;//+hashtable.Count;
                long nps = (time == 0) ? 0 : (1000 * nodeNb / time);
                //int hashfull = (hashMaxSize == 0) ? 0 : (1000 * hashtable.Count / hashMaxSize);
                StringBuilder pv = new StringBuilder("info nodes " + nodeNb + " nps " + nps +  " depth " + maxDepth + " score cp " + bestNode.GetScore() + " time " + watch.ElapsedMilliseconds + " pv");
                while ((depth < maxDepth) && (!bestNode.IsLeave()) )
                {
                    depth++;
                    pv.Append(" " + bestNode.GetPreviousMove().ToString());
                    if (currentPosition.GetTurn())
                    {
                        bestNode = GetMaxNode(bestNode.Children);
                    }
                    else
                    {
                        bestNode = GetMinNode(bestNode.Children);
                    }
                }
                pv.Append(" " + bestNode.GetPreviousMove().ToString());

                System.Console.WriteLine(pv);
            }
        }
        */

        internal void SetPosition(Position pos)
        {
            currentPosition = pos;
        }

        public String ScoreToString(int score)
        {
            if (score < -(VALUE_MATE / 2) || score > (VALUE_MATE / 2))
            {
                String mateIn = "mate ";
                int plies = 0;
                if (score > 0)
                {
                    plies = (VALUE_MATE - score);
                }
                else
                {
                    plies = (-VALUE_MATE - score);
                }
                mateIn = mateIn + plies;
                return mateIn;
            }
            else
            {
                return "cp " + score.ToString();
            }
        }

        internal Position GetCurrentPosition()
        {
            return currentPosition;
        }

        internal int GetBestScore()
        {
            return bestScore;
        }
    }
}